package com.heima.leetcode.practice;

import java.util.HashSet;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 160. 相交链表
 * @date 2025/1/22 12:40
 */
public class E160 {

    /**
     * 存放链表A的节点
     */
    private final HashSet<ListNode> set = new HashSet<>();

    /**
     * <h3>方法一：用HashSet</h3>
     *
     * @param headA 链表A
     * @param headB 链表B
     * @return 相交的节点
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (set.contains(headB)) return headB;
            headB = headB.next;
        }
        return null;
    }

    /**
     * <h3>方法二：去掉不一样长度的，变成等长</h3>
     *
     * @param headA 链表A
     * @param headB 链表B
     * @return 相交的节点
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode currA = headA, currB = headB;
        int lenA = 0, lenB = 0, diff;
        // 1. 统计链表A的长度
        while (currA != null) {
            currA = currA.next;
            lenA++;
        }
        // 2. 统计链表B的长度
        while (currB != null) {
            currB = currB.next;
            lenB++;
        }
        // 3. 计算两个链表长度的差值
        diff = Math.abs(lenA - lenB);
        currA = headA;
        currB = headB;
        // 4. 移动指针，使得两个链表长度相同
        while (diff-- > 0) {
            if (lenA > lenB) currA = currA.next;
            else currB = currB.next;
        }
        // 5. 移动指针，寻找相交节点
        while (currA != null && currB != null) {
            if (currA == currB) return currA;
            currA = currA.next;
            currB = currB.next;
        }
        // 6. 相交节点为空
        return null;
    }

    /**
     * <h3>方法三：对方法二略微优化</h3>
     *
     * @param headA 链表A
     * @param headB 链表B
     * @return 相交的节点
     */
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        ListNode currA = headA, currB = headB;
        // 1. 让其中一个链表先走完
        while (currA != null && currB != null) {
            currA = currA.next;
            currB = currB.next;
        }
        // 2. 让另一个链表走完多出来的节点
        while (currA != null) {
            currA = currA.next;
            headA = headA.next;
        }
        while (currB != null) {
            currB = currB.next;
            headB = headB.next;
        }
        // 3. 寻找相交节点
        while (headA != null && headB != null) {
            if (headA == headB) return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}
